'''
https://leetcode.cn/problems/4-keys-keyboard
'''

from functools import cache


class Solution:
    def maxA(self, n: int) -> int:
        @cache
        def f(i):
            if i == 0:
                return 0
            p1 = 1 + f(i - 1)
            p2 = 0
            # 在j+1, j+2位置进行全选和复制, 然后再j+3, ... , i 位置都进行粘贴
            for j in range(i-1):
                p2 = max(p2, f(j) * (i-j+1-2))
            return max(p1, p2)
        return f(n)